import torch
import torch.nn as nn
import torch.nn.functional as F
from typing import Optional, Tuple, Type

from algorithms.common import MLPBlock, LayerNorm2d


class ImageEncoderViT(nn.Module):
    def __init__(
            self,
            img_size: int = 1024,
            patch_size: int = 16,
            in_chans: int = 3,
            embed_dim: int = 768,
            depth: int = 12,
            num_heads: int = 12,
            mlp_ratio: float = 4.0,
            out_chans: int = 256,
            qkv_bias: bool = True,
            norm_layer: Type[nn.Module] = nn.LayerNorm,
            act_layer: Type[nn.Module] = nn.GELU,
            use_abs_pos: bool = True,
            use_rel_pos: bool = False,
            rel_pos_zero_init: bool = True,
            window_size: int = 0,
            global_attn_indexes: Tuple[int, ...] = (),
    ) -> None:
        """
        :param img_size(int):Input image size.
        :param patch_size(int):Patch size.
        :param in_chans(int):Number of input image channels.
        :param embed_dim(int):Patch embedding dimension.
        :param depth(int):Depth of ViT.
        :param num_heads(int):Number of attention heads in each Vit block.
        :param mlt_radio(float):Radio of mlp hidden dim to embedding dim.
        :param out_chans(int):Number of convolution output channels.
        :param qkv_bias(bool):If True, add a learnable bias to query, key, value.
        :param norm_layer(nn.Module):Normalization layer.
        :param act_layer(nn.Module):Activation layer.
        :param use_abs_pos(bool):If True, use absolute positional embeddings.
        :param use_rel_pos(bool):If True, add relative positional embeddings to the attention map.
        :param rel_pos_zero_init(bool):If True, zero initialize relative positional parameters.
        :param window_size(int):Window size for window attention blocks.
        :param global_attn_indexes(list): Indexes for blocks using global attention.
        """
        super().__init__()
        self.img_size = img_size
        self.patch_embed = PatchEmbed(
            kernel_size=(patch_size, patch_size),
            stride=(patch_size, patch_size),
            in_chans=in_chans,
            embed_dim=embed_dim,
        )
        self.pos_embed: Optional[nn.Embedding] = None
        # 来自PatchEmbed的张量为：
        # (B,(H + 2 × padding − kernel_size) / stride+1,(W + 2 × padding − kernel_size) / stride+1,embed_dim)，
        # 但由于算法中采用默认：padding=[0,0]，kernel_size=[16,16],stride=[16,16],所以简化为（1,H/stride,W/stride,embed_dim)
        # stride的值等于patch_size
        if use_abs_pos:
            self.pos_embed = nn.Parameter(torch.zeros(1, img_size // patch_size, img_size // patch_size, embed_dim))
        self.blocks = nn.ModuleList()
        for i in range(depth):
            block = Block(
                dim=embed_dim,
                num_heads=num_heads,
                mlp_ratio=mlp_ratio,
                qkv_bias=qkv_bias,
                norm_layer=norm_layer,
                act_layer=act_layer,
                use_rel_pos=use_rel_pos,
                rel_pos_zero_init=rel_pos_zero_init,
                window_size=window_size if i not in global_attn_indexes else 0,
                input_size=(img_size // patch_size, img_size // patch_size),
            )
            self.blocks.append(block)
        self.neck = nn.Sequential(
            nn.Conv2d(
                embed_dim,
                out_chans,
                kernel_size=1,
                bias=False,
            ),
            LayerNorm2d(out_chans),
            nn.Conv2d(
                out_chans,
                out_chans,
                kernel_size=3,
                padding=1,
                bias=False,
            ),
            LayerNorm2d(out_chans),
        )

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        x = self.patch_embed(x)
        if self.pos_embed is not None:
            x = x + self.pos_embed
        # 多个block得到的feature_map的shape依然是((B,H,W,C)
        for blk in self.blocks:
            x = blk(x)
        x = self.neck(x.permute(0, 3, 1, 2))  # 卷积层对特征维度进行一个下降，默认变成256
        return x


class Block(nn.Module):
    def __init__(
            self,
            dim: int,
            num_heads: int,
            mlp_ratio: float = 4.0,
            qkv_bias: bool = True,
            norm_layer: Type[nn.Module] = nn.LayerNorm,
            act_layer: Type[nn.Module] = nn.GELU,
            use_rel_pos: bool = False,
            rel_pos_zero_init: bool = True,
            window_size: int = 0,
            input_size: Optional[Tuple[int, int]] = None,
    ) -> None:
        super().__init__()
        # 如果张量是[A,B,C,D],norm_layer接收的变量是nn.LayerNorm((B,C,D))，则会对最后三个维度进行归一化
        # 如果num_layer接收的是一个整型，则根据张量的最后一个维度进行计算
        self.norm1 = norm_layer(dim)
        self.attn = Attention(
            dim,
            num_heads=num_heads,
            qkv_bias=qkv_bias,
            use_rel_pos=use_rel_pos,
            rel_pos_zero_init=rel_pos_zero_init,
            input_size=input_size if window_size == 0 else (window_size, window_size),
        )
        self.norm2 = norm_layer(dim)
        self.mlp = MLPBlock(embed_dims=dim, mlp_dims=int(dim * mlp_ratio), act=act_layer)
        self.window_size = window_size

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        shortcut = x
        x = self.norm1(x)
        if self.window_size > 0:
            H, W = x.shape[1], x.shape[2]
            x, pad_hw = window_partition(x, self.window_size)
        x = self.attn(x)
        if self.window_size > 0:
            x = window_unpartition(x, self.window_size, pad_hw, (H, W))
        x = shortcut + x
        x = x + self.mlp(self.norm2(x))
        return x


class Attention(nn.Module):
    """
    Multi-Head Attention Block with relative position embeddings.
    """

    def __init__(
            self,
            dim: int,
            num_heads: int = 8,
            qkv_bias: bool = True,
            use_rel_pos: bool = False,
            rel_pos_zero_init: bool = True,
            input_size: Optional[Tuple[int, int]] = None,
    ) -> None:
        """
        :param dim(int):Number of input channels
        :param num_heads(int):Number of attention heads.
        :param qkv_bias(bool):If True, add a learnable bias to query, key, value.
        :param use_rel_pos(bool):If True, add relative positional embeddings to the attention map.
        :param rel_pos_zero_init:If True, zero initialize relative positional parameters.
        :param input_size(tuple(int, int) or None):Input resolution for calculating the relative
                positional parameter size
        """
        super().__init__()
        self.num_heads = num_heads
        head_dim = dim // num_heads  # 将整个特征空间划分为多个子空间之间进行注意力计算
        self.scale = head_dim ** -0.5  # 采用缩放因子对查询进行缩放（通常为 1/√(head_dim)），这有助于稳定模型训练。
        self.qkv = nn.Linear(dim, dim * 3, bias=qkv_bias)  # 这里的3是为了分出q,k,v三个维度而进行的升维
        self.proj = nn.Linear(dim, dim)
        self.use_rel_pos = use_rel_pos
        if self.use_rel_pos:
            assert (
                    input_size is not None
            ), "Input size must be provided if using relative positional encoding."
            # initialize relative positional embeddings
            # 假设height-axis方向上的尺寸为H，则范围是[0,H-1]，如果取两个位置i,j，则距离d=i-j。
            # 当i=0,j=H-1，则d=(H-1)-0=H-1
            # 当i=H-1,i=0，则d=0-(H-1)=-H+1
            # 所以相对位置可能存在个数是(H-1)-(-H+1)+1=2H-1
            # width-axis方向上同理
            self.rel_pos_h = nn.Parameter(torch.zeros(2 * input_size[0] - 1, head_dim))
            self.rel_pos_w = nn.Parameter(torch.zeros(2 * input_size[1] - 1, head_dim))

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        B, H, W, _ = x.shape
        # qkv —— (3, B, nHead, H * W, C)
        qkv = self.qkv(x).reshape(B, H * W, 3, self.num_heads, -1)
        # q, k, v —— (B * nHead, H * W, C)
        q, k, v = qkv.reshape(3, B * self.num_heads, H * W, -1).unbind(0)
        #  attn —— (B*nHead,H*W,H*W),k.transpose(-2,-1) —— (B*nHead,C,H*W)
        # 这里根据前面的window_partition方法，实际上是窗口与窗口之间进行注意力分数计算，即注意力，很巧妙。
        attn = (q * self.scale) @ k.transpose(-2, -1)  # -1指的是倒数第一个维度，-2指的是倒数第二个维度。
        if self.use_rel_pos:
            attn = add_decomposed_rel_pol(attn, q, self.rel_pos_h, self.rel_pos_w, (H, W), (H, W))
        attn = attn.softmax(dim=-1)  # 最后一个维度进行softmax
        # attn@v —— (B*nHead,H*W,C),x —— (B,nHead,H,W,C)
        x = (attn @ v).view(B, self.num_heads, H, W, -1).permute(0, 2, 3, 1, 4).reshape(B, H, W, -1)
        x = self.proj(x)
        return x


class PatchEmbed(nn.Module):
    """
    Image to Patch Embedding
    """

    def __init__(
            self,
            kernel_size: Tuple[int, int] = (16, 16),
            stride: Tuple[int, int] = (16, 16),
            padding: Tuple[int, int] = (0, 0),
            in_chans: int = 3,
            embed_dim: int = 768,
    ) -> None:
        """
        :param kernel_size (Tuple): kernel size of the projection layer.
        :param stride (Tuple): stride of the projection layer.
        :param padding (Tuple): padding size of the projection layer.
        :param in_chans (int): Number of input image channels.
        :param embed_dim (int): Patch embedding dimension.
        """
        super().__init__()
        self.proj = nn.Conv2d(in_chans, embed_dim, kernel_size=kernel_size, stride=stride, padding=padding)

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        x = self.proj(x)
        # 重排列，B C H W -> B H W C
        x = x.permute(0, 2, 3, 1)
        return x


def window_partition(x: torch.Tensor, window_size: int) -> Tuple[torch.Tensor, Tuple[int, int]]:
    """
    :param x (tensor): input tokens with [B,H,W,C]
    :param window_size (int): window size.
    :return:
        windows:windows after partition with [B*num_windows,window_size,window_size,C]
        (Hp,Wp):padded height and width before partition
    """
    B, H, W, C = x.shape
    # (H%window_size)计算得到剩余多少个像素，(window_size - H%window_size)计算要补足一个窗口，还差多少个像素
    pad_h = (window_size - H % window_size) % window_size
    pad_w = (window_size - W % window_size) % window_size
    if pad_h > 0 or pad_w > 0:
        # 根据pad_h,pad_w的计算结果进行填充，F.pad所接受的参数x和(0,0,0,pad_h,0,pad_w)
        # x是被填充的对象
        # (0,0,0,pad_h,0,pad_w)，从左到右考虑，并划分(0,0),(0,pad_w),(0,pad_h)，分别对应倒数的维度1，维度2，维度3的padding效果
        # 也就是 C——(0,0)，W——(0,pad_w)，H——(0，pad_h)
        # (0,0)代表在C维度上“左”“右”两边都不做padding
        # (0,pad_w)只在W维度上的右边进行padding，数量为pad_w
        # (0,pad_h)只在H维度上的右边进行padding，数量为pad_h
        x = F.pad(x, (0, 0, 0, pad_w, 0, pad_h))  # 这里的维度是(B,Hp,Hw,C)
    Hp, Wp = H + pad_h, W + pad_w
    x = x.view(B, Hp // window_size, window_size, Wp // window_size, window_size, C)
    # 这里的维度会变成(B*(Hp//window_size)*(Wp//window_size),window_size,window_size,C)
    # 其中(Hp//window_size)*(Wp//window_size)=num_windows，即，窗口的个数。
    windows = x.permute(0, 1, 3, 2, 4, 5).contiguous().view(-1, window_size, window_size, C)

    return windows, (Hp, Wp)


def window_unpartition(
        windows: torch.Tensor,
        window_size: int,
        pad_hw: Tuple[int, int],
        hw: Tuple[int, int],
) -> torch.Tensor:
    """
    # :param windows(tensor): input tokens with [B*num_windows,window_size,window_size,C]
    # :param window_size(int): window size
    # :param pad_hw(Tuple): padded height and width(Hp,Wp)
    # :param hw(Tuple): original height and width (H,W) before padding
    # :return:unpartitioned sequences with [B,H,W,C]
    """
    Hp, Wp = pad_hw
    H, W = hw
    B = windows.shape[0] // (Hp * Wp // window_size // window_size)
    x = windows.view(B, Hp // window_size, Wp // window_size, window_size, window_size, -1)
    x = x.permute(0, 1, 3, 2, 4, 5).contiguous().view(B, Hp, Wp, -1)
    if Hp > H or Wp > W:
        x = x[:, :H, :W, :].contiguous()
    return x


def add_decomposed_rel_pol(
        attn: torch.Tensor,
        q: torch.Tensor,
        rel_pos_h: torch.Tensor,
        rel_pos_w: torch.Tensor,
        q_size: Tuple[int, int],
        k_size: Tuple[int, int],
) -> torch.Tensor:
    """
    Calculate decomposed Relative Positional Embeddings.From paper:'mvitv2'
    # https://github.com/facebookresearch/mvit/blob/19786631e330df9f3622e5402b4a419a263a2c80/mvit/models/attention.py
    # :param attn (Tensor): Attention Map.
    # :param q (Tensor): Query q in the attention layer with shape(B,q_h*q_w,C).
    # :param rel_pos_h (Tensor): relative positional embeddings(Lh,C) for height axis.
    # :param rel_pos_w (Tensor): relative positional embeddings(Lw,C) for width axis.
    # :param q_size (Tuple): spatial sequence size of query q with (q_h,q_w).
    # :param k_size (Tuple): spatial sequence size of key k with (k_h,k_w).
    # :return:attn (Tensor): Attention Map with relative positional embeddings.
    """
    q_h, q_w = q_size
    k_h, k_w = k_size
    Rh = get_rel_pos(q_h, k_h, rel_pos_h)
    Rw = get_rel_pos(q_w, k_w, rel_pos_w)
    B, _, dim = q.shape
    r_q = q.reshape(B, q_h, q_w, dim)
    # einsum,爱因斯坦求和，以“bhwc,hkc->bhwk”为例，对于两个c维度上的元素进行乘积求和，即,rel_h[b,h,w,k]=Σ(c)r_q[b,h,w,c]*Rh[h,k,c]
    rel_h = torch.einsum("bhwc,hkc->bhwk", r_q, Rh)
    rel_w = torch.einsum("bhwc,wkc->bhwk", r_q, Rw)
    attn = (
            attn.view(B, q_h, q_w, k_h, k_w) + rel_h[:, :, :, :, None] + rel_w[:, :, :, None, :]
    ).view(B, q_h * q_w, k_h * k_w)

    return attn


def get_rel_pos(q_size: int, k_size: int, rel_pos: torch.Tensor) -> torch.Tensor:
    """
    Get relative positional embeddings according to the relative positions of q and k sizes.
    实际上是计算query q 和 key k 之间的相对坐标
    :param q_size: size of query q
    :param k_size: size of key k
    :param rel_pos(Tensor): 所有可能的相对位置编码，relative positional embeddings(L,C)
    :return:Extraed positional embeddings according to relative positions
    """
    max_rel_dist = int(2 * max(q_size, k_size) - 1)
    if rel_pos.shape[0] != max_rel_dist:
        # 这里改变rel_pos的shape，从(L,C)->(1,L,C)->(1,C,L)，为了让F.interpolate在最后一维插值
        rel_pos_resized = F.interpolate(
            rel_pos.reshape(1, rel_pos.shape[0], -1).permute(0, 2, 1),
            size=max_rel_dist,
            mode="linear",
        )
        # 这里从(1,C,L)->(C,L)->(L,C)变回来，但已经不是原本的大小了。
        rel_pos_resized = rel_pos_resized.reshape(-1, max_rel_dist).permute(1, 0)
    else:
        rel_pos_resized = rel_pos

    q_coords = torch.arange(q_size)[:, None] * max(k_size / q_size, 1.0)  # [q_size,1]
    k_coords = torch.arange(k_size)[None, :] * max(q_size / k_size, 1.0)  # [1,k_size]
    # TODO q_size和k_size的大小是一样的？
    # 当计算q_coords-kcoords时，q-coords和k-coords都会变为[q_size,k_size]
    relative_coords = (q_coords - k_coords) + (k_size - 1) * max(q_size / k_size, 1.0)
    return rel_pos_resized[relative_coords.long()]
